COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\\M1BASL30\M2SUB\M3NGB30\M4BASI30
C00006 00003	\F34.\F1 Sets as data structures: revisited. Recall the first examination
C00010 ENDMK
C⊗;
\\M1BASL30;\M2SUB;\M3NGB30;\M4BASI30;
\F1


\C\F3CIS 280 Final


\J\F1Good Evening. You should read all questions through thoroughly
before you begin. As always if you or any member of your
\F3C\F2ommittee\F1 on \F3I\F2nstant\F1 \F3S\F2____\F1 Force are
captured by PL/1 the Evaluator will disavow any knowledge of your 
existence. This test will self-destruct in 2 hours and 15 minutes.




\F31.\F1 We wish to extend the language constructs of LISP to allow a more general
form of the conditional expression. We wish to be able to write:

[p\F21\F1→ e\F211\F1;e\F212\F1 ... e\F21i\F1;
p\F22\F1→ e\F221\F1;e\F222\F1 ... e\F22j\F1;
 ...
p\F2n\F1→ e\F2n1\F1;e\F2n2\F1 ... e\F2nm\F1]

The basic semantics is the same as that for simple conditionals: left-to-right
evaluation, looking for the first p\F2k\F1 which has value T.
Now, however, we wish to evaluate a sequence:

e\F2k1\F1;e\F2k2\F1 ... e\F2kj\F1.

The evaluation is to be done in left-to-right order and the value of the extended
conditional is the value of e\F2kj\F1.

Using the original LISP evaluator (where symbol tables were represented as simple
sequences of variable-value pairs), give a representation for such conditionals;
write an evaluator for such conditionals; and extend the compiling algorithm
to produce code for such beasties.




\F32.\F1 Give a precise and careful description of the following:

a. the LISP evaluation process.

b. the difference between compilation and evaluation.

c. the use of symbol tables in LISP to maintain proper bindings of variables.





\F33.\F1 In LISP, atoms are stored uniquely, but non-atomic S-exprs are not
usually stored in this fashion. Do  you see why? If we \F3did\F1 wish
to store S-exprs in such a fashion, what problems do you forsee? For example
would any restrictions need be placed on LISP operations.
Hints that flashed before my eyes: (1) most implementations have
\F4eq[x;x]\F1 give value \F4T\F1 for \F3any\F1 \F4x\F1; however 
\F4eq[(A.B);(A.B)]\F1 is usually
\F4NIL\F1; (2) systems which store S-exprs uniquely depend on an operation called
"hash-consing".

\F34.\F1 Sets as data structures: revisited. Recall the first examination
in which we attempted to describe the mechanisms for implementing
equality on representations of sets.
The Pontiff extolled the virtues of storing sets canonically. Thus sets
which are "equal" are stored in a unique fashion. \F4{A,B,B,C}, {C,B,A},\F1 and
\F4{A,B C}\F1 are all stored as the same representative. Sets may come into existence
in a machine in several ways: they may be read in; there are operations 
to add members; there are operations to delete members.

Assume that we are interested in sets of atoms, and assume the
existence of a predicate \F4orderp[x;y]\F1 telling whether atom, \F4x\F1, is
"greater than" atom \F4y\F1, in some arbitrary order.

Write five LISP functions:

a. A read-in function, \F4canon_eyes[x]\F1 which will take a list of the elements of an
input set and canonize it. Saint-hood is to be dispensed by removing duplicates
and ordering the distinct elements according to \F4orderp\F1.

b. A function, \F4insert[x;s]. s\F1 is a set; \F4x\F1 is an atom. 
The value of \F4insert[x;s]\F1
is a set representing the insertion of \F4x\F1 in \F4s\F1.

c. A function, \F4delete[x;s]\F1, to delete the atom \F4x\F1 from the set \F4s\F1.

d. A predicate \F4member[x;s]\F1 whose effect should be clear.

e. Finally \F4equal_set[u;v]\F1, a predicate to test equality of sets \F4u\F1, 
and \F4v\F1.

Be as clever and frugal with computation as possible, but be sure to
be clear about the trickery you are using.